//import java.util.*;
//
//public class Demo0713 {
//    public static  Queue<BinaryTree.TreeNode> Queue1 = new LinkedList<>();
//    public static void main(String[] args) {
//        BinaryTree binaryTree=new BinaryTree();
//        BinaryTree.TreeNode root=binaryTree.createTree();
//    }
//    // 二叉树前序非递归遍历//循环先打印根 再打印左树 当左树打印完时 打印右树
//    class Solution {
//    }
//        public List<Integer> preorderTraversal(BinaryTree.TreeNode root) {
//            List<Integer> list=new ArrayList<>();
//            Stack<BinaryTree.TreeNode> stack1 = new Stack<>();
//            BinaryTree.TreeNode cur = root;
//            while (cur != null || !stack1.isEmpty()){
//                while (cur != null) {
//                    stack1.push(cur);
//                    list.add(cur.val);
//                    cur=cur.left;
//                }
//                cur=stack1.pop().right;
//            }
//            return list;
//
//
//        }
//    }
//    // 二叉树前序非递归遍历//
//
//    //中序后序还原二叉树 后序的尾部确定根 中序确定左右树 从后序列表中找到第一个根节点 再在中序列表中找到这个根节点，找到后，再从这个根节点的左右展开创建左右树，
//    class Solution {
//        public int postindex=0;
//        public int findinindex(int[] inorder,int key,int inbegin,int inend){
//            for(int i=inbegin;i<=inend;i++){
//                if(inorder[i]==key) return i;
//            }
//            return -1;
//        }
//        public BinaryTree.TreeNode buildTree(int[] inorder, int[] postorder,int inbegin,int inend) {
//            if(inbegin>inend) return null;
//            BinaryTree.TreeNode root=new BinaryTree.TreeNode(postorder[postindex]);
//            int  inindex=findinindex(inorder,postorder[postindex],inbegin,inend);
//            postindex--;
//            root.right=buildTree(inorder,postorder,inindex+1,inend);
//            root.left=buildTree(inorder,postorder,inbegin,inindex-1);
//            return root;
//        }
//        public BinaryTree.TreeNode buildTree(int[] inorder, int[] postorder) {
//            postindex=postorder.length-1;
//            return buildTree(inorder,postorder,0,inorder.length-1);
//        }
//    }
//
//    //中序后序还原二叉树
//
//    //前序中序还原二叉树 前序的头部确定根 中序确定左右树 从前序列表中找到第一个根节点 再在中序列表中找到这个根节点，找到后，再从这个根节点的左右展开创建左右树，
//    class Solution {
//        public int preindex=0;
//        public int findinindex(int[] inorder,int key,int inbegin,int inend){
//            for(int i=inbegin;i<=inend;i++){
//                if(inorder[i]==key) return i;
//            }
//            return -1;
//        }
//        public BinaryTree.TreeNode buildTree(int[] preorder, int[] inorder,int inbegin,int inend) {
//            if(inbegin>inend) return null;
//            BinaryTree.TreeNode root=new BinaryTree.TreeNode(preorder[preindex]);
//            int inindex=findinindex(inorder,preorder[preindex],inbegin,inend);
//            preindex++;
//            root.left=buildTree(preorder,inorder,inbegin,inindex-1);
//            root.right=buildTree(preorder,inorder,inindex+1,inend);
//            return root;
//
//
//        }
//        public BinaryTree.TreeNode buildTree(int[] preorder, int[] inorder) {
//            return buildTree(preorder,inorder,0,inorder.length-1);
//        }
//    }
//
//    //前序中序还原二叉树
//
//    //两个节点的最近公共祖先 找出从根节点 到 待找节点的根的 路径 拿到两个路径组成的栈后 把更长的那个栈弹出元素达到一样长，再同时弹出，当弹出的节点相同时，该节点为最近的根节点。
//    class Solution {
//        public Stack<BinaryTree.TreeNode> stack1=new Stack<>();
//        public Stack<BinaryTree.TreeNode> stack2=new Stack<>();
//        public boolean getpath(BinaryTree.TreeNode root, BinaryTree.TreeNode node, Stack<BinaryTree.TreeNode> stack) {
//            if(root==null || node==null) return false;
//            stack.push(root);
//            if(root==node) return true;
//            if(getpath(root.left,node,stack) || getpath(root.right,node,stack)) return true;
//            else {
//                stack.pop();
//                return false;
//            }
//        }
//        public BinaryTree.TreeNode lowestCommonAncestor(BinaryTree.TreeNode root, BinaryTree.TreeNode p, BinaryTree.TreeNode q) {
//            if(root==null || p==null || q==null){
//                return null;
//            }
//            getpath(root,p,stack1);
//            getpath(root,q,stack2);
//            if(stack1.size()>stack2.size()){
//                int i=stack1.size()-stack2.size();
//                while(i>0){
//                    stack1.pop();
//                    i--;
//                }
//            }else{
//                int i=stack2.size()-stack1.size();
//                while(i>0){
//                    stack2.pop();
//                    i--;
//                }
//            }
//            while(!stack1.empty()){
//                BinaryTree.TreeNode tmp1=stack1.pop();
//                BinaryTree.TreeNode tmp2=stack2.pop();
//                if(tmp1.equals(tmp2)) return tmp1;
//            }
//            return null;
//        }
//    }
//    //两个节点的最近公共祖先
//
////两个节点的最近公共祖先 进行递归 当左右自述返回的都为空时向上返回空 当左右子树返回的都不为空时 该节点即为公共节点 。 当左右其中一个返回空 且其他节点未找到 说明此时的p q都在左树或右树上 再向下递归 直到其中一个节点为根节点 而另一节点在左树或右树上 次数返回的根节点 即为最近的公共节点。
//class Solution {
//public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        /**
//         注意p,q必然存在树内, 且所有节点的值唯一!!!
//         递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root
//         表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:
//         1. 左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
//         2. 如果左右子树返回值只有一个不为null, 说明只有p和q存在与左或右子树中, 最先找到的那个节点为LCA
//         3. 左右子树返回值均为null, p和q均不在树中, 返回null
//         **/
//        if(root == null || root == p || root == q) return root;
//        TreeNode left = lowestCommonAncestor(root.left, p, q);
//        TreeNode right = lowestCommonAncestor(root.right, p, q);
//        if(left == null && right == null) return null;
//        else if(left != null && right != null) return root;
//        else return left == null ? right : left;
//        }
//        }
////两个节点的最近公共祖先
//
//    //二叉树的层序遍历II  先把根节点放进队列 然后弹出根节点 再把根节点的左右树 放进队列 这时候可以求出第二层的长度就是 放完左右树时的长度 那么第三层的长度也就是第二层的根全部弹出完成的时候的队列长度 以此类推， 因为倒序，把每一层的列表放进栈里 求出每层长度 当上一层长度减完时，当前队列
//    class Solution {
//        public Stack<List<Integer>> stack1=new Stack<>();
//        // public Stack<Integer> stack2=new Stack<>();
//        public Queue<BinaryTree.TreeNode> Queue1 = new LinkedList<>();
//        public List<List<Integer>> levelOrderBottom(BinaryTree.TreeNode root) {
//            List<List<Integer>> list2=new ArrayList();
//            if(root==null) return list2;
//            Queue1.offer(root);
//            while(!Queue1.isEmpty()){
//                int size=Queue1.size();
//                List<Integer> list1=new ArrayList();
//                while(size>0 && !Queue1.isEmpty()){
//                    BinaryTree.TreeNode tmp=Queue1.poll();
//                    list1.add(tmp.val);
//                    size--;
//                    if(tmp.left!=null) Queue1.offer(tmp.left);
//                    if(tmp.right!=null) Queue1.offer(tmp.right);
//                }
//                stack1.push(list1);
//            }
//            while(!stack1.empty()){
//                list2.add(stack1.pop());
//            }
//            return list2;
//        }
//    }
//    //二叉树的层序遍历II
//
//    //二叉树的层序遍历
//    class Solution {
//        public Queue<BinaryTree.TreeNode> Queue1 = new LinkedList<>();
//        public List<List<Integer>> levelOrder(BinaryTree.TreeNode root) {
//            List<List<Integer>> list2=new ArrayList();
//            if(root==null) return list2;
//            Queue1.offer(root);
//            while(!Queue1.isEmpty()){
//                int size=Queue1.size();
//                List<Integer> list1=new ArrayList();
//                while(size>0 && !Queue1.isEmpty()){
//                    BinaryTree.TreeNode tmp=Queue1.poll();
//                    list1.add(tmp.val);
//                    size--;
//                    if(tmp.left!=null) Queue1.offer(tmp.left);
//                    if(tmp.right!=null) Queue1.offer(tmp.right);
//                }
//                list2.add(list1);
//            }
//            return list2;
//
//    //二叉树的层序遍历
//}
